๐Ÿ‘ฉโ€๐Ÿ’ป 62050. ์ง€ํ˜• ์ด๋™

@Seongukbaek Posted July 31, 2022 ยท Updated July 31, 2022 ยท 4 min read

๋ฌธ์ œ

Programmers - ์ง€ํ˜• ์ด๋™

๐Ÿ“ Logic

private void bfs(int x, int y) {} private int find(int n) {} private void merge(int n1, int n2) {}
  • BFS๋ฅผ ์ˆ˜ํ–‰ํ•ด์„œ ์ง€ํ˜•๋ณ„๋กœ ๋ฒˆํ˜ธ๋ฅผ ๋งค๊ธด๋‹ค.

    • ์ˆ˜ํ–‰ํ•˜๋ฉด์„œ, ๋†’์ด ์ฐจ๊ฐ€ ํฐ ์ง€ํ˜•์„ ์šฐ์„ ์ˆœ์œ„ ํ์— ๋„ฃ์–ด์ค€๋‹ค.
  • ์ดํ›„, ๋†’์ด์ฐจ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ๋œ ์šฐ์„ ์ˆœ์œ„ ํ์— ์žˆ๋Š” ์ง€์—ญ์„ ํ•ฉ์ณ์ฃผ๋ฉด์„œ ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•ด MST๋ฅผ ๊ตฌํ•˜๋ฉด์„œ ์‚ฌ๋‹ค๋ฆฌ์˜ ์ดํ•ฉ์„ ๊ตฌํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Node { int x; int y; public Node(int x, int y) { this.x = x; this.y = y; } } class Square implements Comparable<Square> { int from; int to; int diffDist; public Square(int from, int to, int diffDist) { this.from = from; this.to = to; this.diffDist = diffDist; } @Override public int compareTo(Square s) { return Integer.compare(this.diffDist, s.diffDist); } } class Solution { private static int N; private static int[] parent; private static Queue<Square> pq = new PriorityQueue<>(); private static int[][] visited; private static int[][] land; private static int height; private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private static int areaN; public int solution(int[][] land, int height) { this.N = land.length; this.height = height; this.land = land; this.visited = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (visited[i][j] == 0) { areaN++; bfs(i, j); } this.parent = new int[areaN + 1]; for (int i = 0; i <= areaN; i++) parent[i] = i; int answer = 0; while(!pq.isEmpty()) { Square s = pq.poll(); int f = s.from; int t = s.to; int d = s.diffDist; // ๊ฐ™์€ ๋ถ€๋ชจ, ์ฆ‰ ์‚ฌ์ดํด์„ ํ˜•์„ฑํ•˜๊ฑฐ๋‚˜, ํ˜น์€ ๋ฐฉ๋ฌธํ•œ ์  ์—†๋Š” ์ง€ํ˜•์ด๋ผ๋ฉด ํŒจ์Šค if (find(f) == find(t) || (f == 0 || t == 0)) continue; else { // ๋ถ€๋ชจ๋ฅผ ๊ฐ™๊ฒŒ, ์ฆ‰ ์‚ฌ๋‹ค๋ฆฌ๋ฅผ ๋†“๊ณ  ์ด๋™ํ–ˆ์Œ์„ ์˜๋ฏธ! merge(f, t); answer += d; } } return answer; } // ์ด๋™ ๊ฐ€๋Šฅํ•œ ์ง€ํ˜•์— ๋ฒˆํ˜ธ ๋งค๊ธฐ๊ธฐ private void bfs(int x, int y) { visited[x][y] = areaN; Queue<Node> queue = new LinkedList<>(); queue.offer(new Node(x, y)); while(!queue.isEmpty()) { Node node = queue.poll(); int tmpX = node.x; int tmpY = node.y; for (int[] d : dir) { int nx = tmpX + d[0]; int ny = tmpY + d[1]; if (!isIn(nx, ny)) continue; int diff = Math.abs(land[tmpX][tmpY] - land[nx][ny]); // ์ง€ํ˜• ๊ฐ„์˜ ์ฐจ๊ฐ€ ๋†’์ด๋ณด๋‹ค ํฌ๊ณ , ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์ง€์—ญ์ด๋ผ๋ฉด ์‚ฌ๋‹ค๋ฆฌ๋ฅผ ๋†“์•„์•ผ ํ•  ์ˆ˜๋„ ์žˆ๋‹ค. if (diff > height) { if (visited[nx][ny] != 0) pq.offer(new Square(visited[tmpX][tmpY], visited[nx][ny], diff)); continue; } // ์ง€ํ˜• ๊ฐ„์˜ ์ฐจ๊ฐ€ ๋†’์ด๋ณด๋‹ค ํฌ์ง€ ์•Š์€ ๊ฒฝ์šฐ, // ๋ฐฉ๋ฌธํ•œ ์ง€ํ˜•์ด๋ผ๋ฉด ํŒจ์Šค if (visited[nx][ny] != 0) continue; // ๋ฐฉ๋ฌธํ•œ ์  ์—†๋Š” ์ง€ํ˜•์ธ ๊ฒฝ์šฐ ๋ฒˆํ˜ธ ๋งค๊ธฐ๊ธฐ else { visited[nx][ny] = areaN; queue.offer(new Node(nx, ny)); } } } } private boolean isIn(int x, int y) { return x >= 0 && x < N && y >= 0 && y < N; } // ์žฌ๊ท€๋ฅผ ์ด์šฉํ•ด ๋ถ€๋ชจ ์ง€ํ˜• ๋ฒˆํ˜ธ ์ฐพ๊ธฐ private int find(int n) { if (parent[n] == n) return n; else return parent[n] = find(parent[n]); } private void merge(int n1, int n2) { n1 = find(n1); n2 = find(n2); if (n1 == n2) return; if (n1 > n2) parent[n1] = n2; else parent[n2] = n1; } }

โœ๏ธ Review

  • ์ง€์—ญ์„ ๋‚˜๋ˆ„๊ณ , ์„œ๋กœ ๋‹ค๋ฅธ ์ง€์—ญ์ด ๋งž๋‹ฟ๋Š” ๊ณณ์„ ํ›„๋ณด๋กœ ์ €์žฅํ•ด๋‘๊ณ  ์ด๊ฒƒ๋“ค์„ ๊ฐ€์ง€๊ณ  ์‚ฌ๋‹ค๋ฆฌ ๋น„์šฉ์„ ๊ณ„์‚ฐํ•ด๋ด์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์€ ํ–ˆ์ง€๋งŒ ์–ด๋–ป๊ฒŒ ํ•ด์•ผํ• ์ง€ ๊ฐ์ด ์•ˆ ์žกํ˜”๋‹ค.
  • ๊ฒŒ์‹œํŒ์„ ์ฐธ๊ณ ํ•˜๋‹ˆ MST๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ๊ด€๊ฑด์ธ ๋ฌธ์ œ์˜€๊ณ , ์ฐธ๊ณ ๋ฅผ ํ†ตํ•ด ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค ...
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€